package 数据结构.章节09;

import java.util.HashSet;

/**
 * @author 挚爱之夕
 * @date 2021/10/10 - 10 - 10 - 22:27
 * @Description: 数据结构.章节09
 * @Version: 1.0
 */
public class _152_删除重复链表节点 {
    private static class Node{
        Object value;
        Node next;
        public Node(Object value) {
            this.value = value;
        }
    }
    public static void main(String[] args) {
        int[] a = new int[]{1,3,4,7,3,4,3};
        Node head = new Node(null); //哑元
        //创建链表
        Node p = head;
        for (int j : a) {
            p.next = new Node(j);
            p = p.next;
        }
        //检验是否成功创建
        p = head.next;
        while(p != null){
            System.out.println(p.value);
            p = p.next;
        }
        System.out.println("-------------------");
        //执行去重操作
        removeRepeated1(head);
        //检验是否去重成功
        p = head.next;
        while(p != null){
            System.out.println(p.value);
            p = p.next;
        }
    }
    //使用hash集合
    private static void removeRepeated1(Node head)
    {
        Node p = head.next;
        Node pre = head;
        HashSet<Object> set = new HashSet<Object>();
        while(p != null){
            if(set.contains(p.value)){
                pre.next = p.next;  //删除重复
            }else{//pre记录p，p后移找重复
                set.add(p.value);
                pre = p;
            }
            p = p.next;
        }
    }
    //不新建存储结构：n*n
    private static void removeRepeated2(Node head){
        Node p = head.next;
        Node last;
        Node pre ;
        Node cur;
        while(p!=null&&p.next!=null){
            last = p;
            pre = last;
            cur = p.next;
            while(cur!=null){
                if(last.value == cur.value){
                    pre.next = cur.next;
                }
                pre = cur;
                cur = cur.next;
            }
            p = p.next;
        }
    }
}
